Background Description
The theory of Fourier transformation is fundamental to many undergraduate engineering and science curricula. The Fourier transform is a method of transferring a time domain signal into the frequency domain. A time function can be represented by x(t) where t represents time (e.g., in seconds). If u represents the corresponding frequency variable, with units of cycles per second or Hertz, then X(u) is the representation of x(t) in the frequency domain. The most common way to obtain X(u) from x(t) is by the process of Fourier transformation. In human speech, for example, the Fourier transform of a man's voice will typically contain lower frequency components than a child's voice. Thus, the Fourier transform of a man's voice as represented, for example, by an electronic signal from a microphone would generally have a larger magnitude at lower frequencies than that of a child's voice. The concept of frequency applies to numerous other types of signals also. Electromagnetic waves in the visible spectrum have different colors corresponding to the frequency of the electromagnetic wave frequency (vibration). Thus, the magnitude of the Fourier transform of the temporal electromagnetic vibrations will, in the visible range, result in a plot of the color components of the signal.
As explained in the tutorial, by L. Cohen in "Time-frequency distributions--a review", Proceedings of the IEEE, vol. 77, pp. 941-981 (1989), there are many instances where there is a need to monitor the frequency components (or the Fourier transform) of a signal with respect to time. This is especially important when the character of the signal is changing with respect to time. Such signals are referred to as nonstationary signals. Common speech and music are both examples of nonstationary signals. A sound which does not change in time, such as an elongated tone or the roar from a waterfall, are examples of stationary signals. The temporally changing (i.e. nonstationarity) of colors during a sun set is an example of an electromagnetic nonstationary signal. The fundamental Fourier transform does not allow for the straightforward analysis of nonstationary signals. Other techniques, collectively called time-frequency representations (hereinafter TFR's), are required.
Note that humans perceive sound in both time and frequency. Music, for example, is written as a TFR. Notes can be viewed as a frequency representation. The placement of these notes side by side then represents a temporal sequence of frequency. Spectrograms are probably the most commonly used scientific TFR's for representation of signals. L. Cohen in "Time-frequency distributions--a review", Proceedings of the IEEE, vol. 77, pp. 941-981 (1989) discusses a class of generalized TFR's (hereinafter GTFR's). The zamogram of Zhao, Atlas and Marks reported in "Application of the generalized time-frequency representation to speech signals analysis", Proceedings of the IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 517-519, Victoria, B. C. Canada, June 4-5, 1987 and in "The use of cone-shape kernels for generalized time-frequency representations of nonstationary signals", IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. 38, pp. 1084-1091 (1990) is a GTFR with quite good resolution in both time and frequency that can be architecturally configured to use the sliding window Fourier transform as a component.
As discussed, for example, in A. Papoulis, Signal Analysis, McGraw Hill, New York (1977), sliding window Fourier transforms and spectrograms are conventionally computed using windows, such as Hanning, Hamming or Blackman windows. The choice of the window determines the properties of the sliding window Fourier transform or spectrogram well known to those skilled in the art. This patent contains computationally efficient methods and corresponding architectures for generating sliding window Fourier transforms and spectrograms.
Signals can either be continuous functions of time or can be a sequence of number generated from sampling a continuous time signal or a processed version thereof. Methods and architectures for processing continuous and discrete time signals are parallel topics. Indeed, the topics are many times taught simultaneously at the undergraduate electrical engineering level. Thus, although the methods and architectures of the present invention are described herein with respect to discrete time signals, they can be straight-forwardly extended to continuous time by one skilled in the art.
The sliding window Fourier transform of a discrete signal x[n], corresponding to a window, .omega.[k], is ##EQU1## where u is the frequency variable and L parameterizes the duration of the window. The function .vertline.S[n;u].vertline..sup.2 is called the spectrogram.
Temporally sliding windows can be viewed as filter impulse responses that are typically of finite duration. Windowing is used in other applications including data smoothing and finite impulse response (FIR) filter design.
Digitally, the Fourier transform can be computed using a discrete Fourier transform (DFT). DFT's can be used to generate short term Fourier transforms. When the duration of a signal to be transformed is long, the fast Fourier transform (FFT) computes the Fourier transform in significantly fewer operations (i.e. multiplications and additions). The FFT is also used in the generation of sliding window Fourier transforms and spectrograms. Typically, the sliding window Fourier transform or spectrogram is decimated in time. In other words, the output is not computed at each point in discrete time. Rather, the output is computed every few points in discrete time.
Recursive generation of rectangularly windowed sliding window Fourier transforms has been disclosed in U.S. Pat. No. 4,023,028 issued to Dillard on May 10, 1977. The basic ides of the sliding rectangular window is best introduced by the following example. Consider the series of numbers . . . 2,4,1,3,0,1,4,1,2,0. The sum of the bold numbers in the series . . . 2,4,1,3,0,1,4,1,2,0 is 14. The window is moved over one unit and the result is . . . 2,4,1,3,0,1,4,1,2,0. The new sum can, of course, be generated by adding the numbers again. More efficiently, however, the odd numbers (4) can be subtracted from the sum and the new number (2) added. This is the basic concept used in the sliding rectangular window generation of the sliding window Fourier transform. With slight modification, exponentially shaped windows can also be thus computed.
Both rectangular and exponential windows have limited application. As is summarized by W. S. Wu, K. F. Cheung and R. J. Marks II, "Multidimensional projection windows", IEEE Transactions on Circuits and Systems, vol. 35, pp. 1186-1172 (1988), the performance of a window is dictated by its resolution versus leakage tradeoff. The most commonly used windows display a balanced trade off between good time and frequency resolution. The rectangular and exponential windows do not. The rectangular window, for example, displays quite poor frequency leakage properties. More typically, the numbers within the window are multiplied by a symmetric array of numbers prior to summation. This array of numbers is referred to as a window. Commonly used windows are Hanning, Hamming and Blackman windows referred to above. This patent claims recursive computational methods and architectures for generation of such sliding window Fourier transforms using tapered windows.